package seqlist;

import java.util.Arrays;

// 动态数组
public class DynamicArrayReview {
    // 实际元素还是在int[]数组中存储
    private int[] elementData;
    // size干嘛的？size实际上描述了当前动态数组中实际存储的有效元素个数
    private int size;

    public DynamicArrayReview() {
        this.elementData = new int[10];
    }

    public DynamicArrayReview(int size) {
        this.elementData = new int[size];
    }

    public int getSize() {
        return size;
    }

    public void addIndex(int index,int data) {
        // index = 0 -> 在数组的头部添加
        // index = size -> 在数组的尾部添加
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }
        // 判断此时数组是否已满
        if (size == elementData.length) {
            // 扩容
            grow();
        }
        for (int i = size - 1;i >= index;i--) {
            // 数据搬移
            elementData[i + 1] = elementData[i];
        }
        // index位置的元素已经空出来了，直接插入新元素
        elementData[index] = data;
        size ++;
    }

    public void addFirst(int data) {
        addIndex(0,data);
    }

    public void addLast(int data) {
        addIndex(size,data);
    }

    public void removeIndex(int index) {
        // 先判断临界条件
        if (index < 0 || index >= size) {
            System.err.println("remove index illegal!");
            return;
        }
        // 此时index是合法滴
        for (int i = index;i < size - 1;i ++) {
            // 将后一个元素覆盖前一个元素
            elementData[i] = elementData[i + 1];
        }
        size --;
        // 确保数组中最后元素也还原为默认值
        elementData[size] = 0;
    }

    /**
     * 按照值删除元素
     * @param value
     */

    public void removeValue(int value) {
        for (int i = 0; i < size; i++) {
            // 此时索引i对应的元素就是待删除的元素
            // [2,2,2,1] => value = 2
            // 由于此处可能会出现多个连续的待删除元素
            // 如果此时数组[2,2,2,1]
            while (elementData[i] == value) {
                removeIndex(i);
            }
        }
    }

    public static void main(String[] args) {
        DynamicArrayReview dynamicArrayReview = new DynamicArrayReview();
        dynamicArrayReview.addLast(1);
        dynamicArrayReview.addLast(2);
        dynamicArrayReview.addLast(2);
        dynamicArrayReview.addLast(2);
        // [1,2,2,2]
        System.out.println(dynamicArrayReview);
        dynamicArrayReview.removeValue(2);
        // []
        System.out.println(dynamicArrayReview);
    }

    @Override
    public String toString() {
        String ret = "[";
        for (int i = 0; i < size; i++) {
            ret += elementData[i] + ", ";
        }
        ret += "]";
        return ret;
    }

    private void grow() {
        // 数组拷贝
        elementData = Arrays.copyOf(elementData,elementData.length << 1);
    }
}
